﻿// 0826train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标
 数组中的每个元素代表你在该位置可以跳跃的最大长度
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标
 */
int solve01(vector<int>&nums)
{
	int right_most = 0;
	for (int i=0; i<nums.size(); i++)
	{
		//可到达
		if (i<=right_most)
		{
			right_most = max(right_most, i + nums[i]);

		}
	}
	if (right_most >= nums.size() - 1)
	{
		return true;
	}
	return false;
	//solve01
}

/*
 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度
换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 */
int solve02(vector<int>&nums)
{
	//初始化当前位置now_pos, 右边界right, 步数step
	int now_pos = 0, step = 0;
	int right = now_pos + nums[now_pos];

	while (now_pos<nums.size()-1)
	{
		if (right>=nums.size()-1)
		{
			step += 1;
			break;
		}

		//遍历now_pos+1到right，更新下一个位置和右边界
		int next_pos = now_pos, next_right = right;
		for (int i=next_pos+1; i<=right; i++)
		{
			if (i+nums[i]>next_right)
			{
				next_pos = i;
				next_right = i + nums[i];
			}
		}
		now_pos = next_pos;
		right = next_right;
		step += 1;

	}
	return step;
	//solve02
}

int main()
{
	{
		//nums = [2,3,1,1,4] 2
		//[2,3,0,1,4] 2
		//[2,1]
		vector<int>nums = { 2,3,0,1,4 };
		cout << solve02(nums);

		return 0;
	}
	//nums = [2,3,1,1,4]
	vector<int>nums = { 2,3,1,1,4 };
	cout << solve01(nums);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
